package cn.lena.algorithm;

//动态规划算法
public class Dynamic {


	//数字三角形（递归思想+记忆数组避免运算重复）
	//传入的ij是三角形的起始点
	public static void digTalTriangleByRecursion(int i,int j,int tri[][]){
		int a = tri.length;
		int b=tri[0].length;
		int maxSum[][]=new int[a][b];
		for (int m=0;m<a;m++){
			for (int n=0;n<b;n++) {
				maxSum[m][n] = -1;
				//System.out.printf("%d",maxSum[m][n]);
			}
			//System.out.println();
		}
		System.out.println("最大值是:"+maxNum(i,j,tri,maxSum));
	}
	private static int maxNum(int i,int j,int tri[][],int maxSum[][]){
		//	System.out.println("此时i="+i+"j="+j);
		if(maxSum[i][j]!=-1){	//已经计算过最大值
			//	System.out.println("值为="+maxSum[i][j]);
			return maxSum[i][j];
		}
		if(i==tri.length-1){
			maxSum[i][j]=tri[i][j];
		}else{
			int x=maxNum(i+1,j,tri,maxSum);
			int y=maxNum(i+1,j+1,tri,maxSum);
			//		System.out.println("左边的数="+x+"-----右边的数="+y);
			maxSum[i][j]=Math.max(x,y)+tri[i][j];
		}
		//	System.out.println("此时i="+i+"j="+j);
		//	System.out.println("最大值是"+maxSum[i][j]);
		return maxSum[i][j];
	}

	//数字三角形（递推+定义新的一维数组不断覆盖）
	public static int digTalTriangleByPushOptimize(int tri[][]){
		int temp[]=new int[tri[0].length];
		for(int x=0;x<tri[0].length;x++){
			temp[x]=tri[tri.length-1][x];		//将最后一行复制给数组temp
	//		System.out.println(temp[x]);
		}
		for (int x=tri.length-2;x>=0;x--) {        //最后一行无需计算，本身就是最大值
		//	System.out.println("第"+x+"列");
			for(int y=0;y<temp.length-1;y++) {
			//	temp[y] = tri[x][y] + Math.max(tri[x + 1][y], tri[x + 1][y + 1]);
				temp[y] = tri[x][y] + Math.max(temp[y], temp[y+1]);
			//	System.out.println("最大值" + temp[y]);
			}
		}
		return temp[0];
	}

	//数字三角形（递推+在原数组进行覆盖）
	public static int digTalTriangleByPush(int i,int j,int tri[][]){
		//直接在原数组进行操作，最后一行不用操作
		for (int x=tri.length-2;x>=0;x--){		//最后一行无需计算，本身就是最大值
			//当y为最后一个索引时，求y+1位会产生溢出，而除了最后一行外，每行最后一个存的数字没有意义，因此忽略不求最后一个索引最大值。
			for (int y=0;y<tri[0].length-1;y++){
				tri[x][y] += Math.max(tri[x+1][y],tri[x+1][y+1]);	//等于当前数值+左右最大数值
			}
		}
		return tri[i][j];
	}

	//最长上升子序列
	public static int longestUpSubsequence(int sub[]){
		int max[]=new int[sub.length];	//定义一个和sub一样长的数组，存储以当前序列为终点的最大上升子序列。
		for (int i=0;i<max.length;i++) {
			max[i] = 1;
		}
		for (int i=2;i<sub.length;i++){
			for (int j=0;j<i;j++){
				if (sub[j]<sub[i])
					max[i]=Math.max(max[i],max[j]+1);
			}
		}
		int maxLen=0;	//存储最长子序列
		for (int i=0;i<max.length;i++){
			maxLen=Math.max(maxLen,max[i]);
		}
		return maxLen;
	}

	//最长公共子序列
	public static int longestPublishSubsequence(char s1[],char s2[]){
		int len1=s1.length;
		int len2=s2.length;
		int maxLen[][]=new int[len1+1][len2+1];		//需要大1：(i,j)表示i前j前的最长公共子序列，只有(len1+1,len2+1)才表示最后一个比较的结果
		//初始状态
		for (int i=0;i<len1;i++)
			maxLen[i][0]=0;
		for (int i=0;i<len2;i++)
			maxLen[0][i]=0;
		//求出每个子问题的最长公共子序列
		for (int i=1;i<=len1;i++){
			for (int j=1;j<=len2;j++){
				if (s1[i-1]==s2[j-1])
					maxLen[i][j]=maxLen[i-1][j-1]+1;
				else
					maxLen[i][j]=Math.max(maxLen[i][j-1],maxLen[i-1][j]);
			}
		}
		//获得当前最长公共子序列
		int max=0;
		for (int i=1;i<len1+1;i++) {
			for (int j = 1; j < len2+1; j++) {
				max=Math.max(max,maxLen[i][j]);
			}
		}
		return max;
	}

	//背包问题
	public static void knapsackProblem(int w[],int val[],int m){
		int n = val.length; //物品的个数
		//创建二维数组，
		//v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
		int[][] v = new int[n+1][m+1];
		//为了记录放入商品的情况，我们定一个二维数组
		int[][] path = new int[n+1][m+1];

		//初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
		for(int i = 0; i < v.length; i++) {
			v[i][0] = 0; //将第一列设置为0
		}
		for(int i=0; i < v[0].length; i++) {
			v[0][i] = 0; //将第一行设置0
		}

		int a=0,b=0;
		//根据前面得到公式来动态规划处理
		for(int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的
			for(int j=1; j < v[0].length; j++) {//不处理第一列, j是从1开始的
				if (w[i-1]>j){
					v[i][j]=v[i-1][j];	//和上一个物品的最大价值一样
				}else{
					a=v[i-1][j];	//上一个物品的最大价值
					b=v[i-1][j-w[i-1]]+val[i-1];	//剩余空间所能放下最大价值+当前物品
					v[i][j]=a>b?a:b;
					path[i][j] = 1;		//将j重量时，所存入的i商品记录下来
				}
			}
		}

		//输出一下v 看看目前的情况
		for(int i =0; i < v.length;i++) {
			for(int j = 0; j < v[i].length;j++) {
				System.out.print(v[i][j] + " ");
			}
			System.out.println();
		}

		System.out.println("============================");

		//最后一个结果输出的重量
		int i = path.length - 1; //行的最大下标
		int j = path[0].length - 1;  //列的最大下标
		System.out.printf("最后一个背包放入的商品有:");
		while(i > 0 && j > 0 ) {
			//	从path的 最后 开始找。当背包空间j=0时，不再进入循环。	i不可能减到剩余0，因为在当前i遍历到0之前，在本列j中一定会出现path=1。
			if(path[i][j] == 1) {
				System.out.printf("第%d个商品 ", i);
				j = j - w[i-1]; 		//减去当前的商品到的重量
			}
			i--;
		}

	}

}
